'''
https://leetcode.cn/problems/minimum-knight-moves
'''
from collections import deque
from functools import cache


class Solution:
    # bfs
    def minKnightMoves(self, x: int, y: int) -> int:
        q = deque([(0, 0)])
        visited = set()
        step = 0
        while q:
            for _ in range(len(q)):
                i, j = q.popleft()
                if (i, j) == (x, y):
                    return step
                for tx, ty in [(i+2,j+1), (i+2, j-1), (i-2,j+1), (i-2, j-1), (i+1, j+2), (i+1, j-2), (i-1, j+2), (i-1, j-2)]:
                    if (tx, ty) in visited: continue
                    visited.add((tx, ty))
                    q.append((tx, ty))
            step += 1
        return -1

    # dp
    def minKnightMoves2(self, x: int, y: int) -> int:
        @cache
        def dfs(x, y):
            if x + y == 0:
                # 边界条件：(0, 0)
                return 0
            elif x + y == 2:
                # 边界条件：(1, 1), (0, 2), (2, 0)
                return 2
            else:
                return min(dfs(abs(x - 1), abs(y - 2)), dfs(abs(x - 2), abs(y - 1))) + 1
        return dfs(abs(x), abs(y))

    # 双向bfs
    def minKnightMoves3(self, x: int, y: int) -> int:
        if x == 0 and y == 0: return 0
        small_nodes = {(0, 0)}
        large_nodes = {(x, y)}
        visited = {(0, 0), (x, y)}
        step = 0
        while small_nodes:
            temp_nodes = set()
            for i, j in small_nodes:
                for tx, ty in [(i+2,j+1), (i+2, j-1), (i-2,j+1), (i-2, j-1), (i+1, j+2), (i+1, j-2), (i-1, j+2), (i-1, j-2)]:
                    if (tx, ty) in large_nodes:
                        return step + 1
                    if (tx, ty) in visited: continue
                    visited.add((tx, ty))
                    temp_nodes.add((tx, ty))
            step += 1
            small_nodes = temp_nodes if len(temp_nodes) <= len(large_nodes) else large_nodes
            large_nodes = large_nodes if len(temp_nodes) <= len(large_nodes) else temp_nodes
        return -1

x, y = 2, 4
print(Solution().minKnightMoves3(x, y))
